
/*=============================================================*
 *	Written By: Joseph Conrad Stack
 *	Unity ID:   jcstack   
 *	Date:       4-29-03
 *
 *	Description:
 *	
 *=============================================================*/
import java.util.*;
import java.io.*;
import java.lang.*;



public class ExpressionTree {
    public Stack operators = new Stack();
    public Stack operands = new Stack();
    public BinNode tp;
    public int State = 1;

    /** Constructs a new instance of an expression tree.
     * This constructor takes a String as a parameter containing an
     * algebraic expression.  It parses this expression and and build a new
     * instance of an expression tree.
     *
     * @param expr The String object containing the algebraic expression to
     * be parsed.
     */
    public ExpressionTree( String expr )
    {

        try {
            BufferedReader B = new BufferedReader(new FileReader(expr));
            String Line="";
            while ((Line = B.readLine()) != null) {
                
                StringTokenizer ST = new StringTokenizer(Line);
                while (ST.hasMoreTokens()) {
                    String temp = ST.nextToken();

                    if (temp.equals("(")) {
                        operators.push(temp);
                    } 
                    
                    else if (temp.equals(")")) {
                        while (!(operators.peek()).equals("("))
                            buildSubTree();
                        operators.pop();
                    } 
                    
                    else if (temp.equals("%") || temp.equals("+") || temp.equals("-") || temp.equals("^") || temp.equals("/") || temp.equals("*")) {
                        //System.out.println("got an operator:"+ temp);
                        while ((!operators.isEmpty()) && checkPres(operators.peek()) >= checkPres(temp))
                            buildSubTree();
                        operators.push(temp);
                    } 
                    
                    else {
                        //System.out.println("got an operand:" + temp);
                        LeafNode newRoot = new LeafNode((Object)temp);
                        operands.push(newRoot);
                    }

                }                      
            }
            // end Constructor
        } catch (IOException e) {
            System.out.println("something is wrong:" + e);
        }
        //System.out.println("built the tree!");
     while(!(operators.isEmpty()))
         buildSubTree();
     tp = (BinNode)operands.pop();
     //preorder(tp);
    }




    public void buildSubTree()
    {
        BinNode rt = (BinNode)operands.pop();
        //System.out.println("this is the right operand:" + (rt.element()).toString());
        BinNode lt = (BinNode)operands.pop();
        //System.out.println("this is the left operand:" + (lt.element()).toString());

        Character rootVal = new Character(((operators.pop()).toString()).charAt(0));

        //System.out.println("this is the subRoot:" + rootVal.toString());
        IntNode subRoot = new IntNode(rootVal,lt,rt);
        operands.push(subRoot);
    }

    public int checkPres(Object check){
        int pres = 0;
        String check1 = (String)check;
        if (check1.equals("+") || check1.equals("-"))
            pres = 1;
        if (check1.equals("*") || check1.equals("/") || check1.equals("%"))
            pres = 2;
        if (check1.equals("^"))
            pres = 3;

        return pres;

    }


    /** Performs a preorder traversal of the expression tree.
 * This method will return a String containing theexpression in its
 * prefix representation.
 *
 * @return The prefix notation for the expression stored in the tree.
 */
    public String preorder()
    {
        BinNode tRoot = tp;
        String output = "";
        operands.push(tp);
        while( !(operands.isEmpty()) )
        {
            while(tRoot.left() != null)
            {
               output += tRoot.element().toString();
                operands.push(tRoot);
                tRoot = tRoot.left();
                if (tRoot.left() == null)
                   output += tRoot.element().toString();
            }
            tRoot = (BinNode)operands.pop();
    	    tRoot = tRoot.right();
            if(tRoot.left() == null)
            	output += tRoot.element().toString();
        }

        return output;
    
    }
       

        

    /** Performs a postorder traversal of the expression tree.
     * This method will return a String containing the expression in its
     * postfix representation.
     *
     * @return The postfix notation for the expression stored in the tree.
     */
    public String postorder()
    {
    BinNode postRoot = tp;
    String output = "";
    //operators.push(postRoot);
    State = 1;
    while(State != 10){
        switch (State) {
        case 1:if(postRoot.left() == null){
            State = 2;
            break;
        }else if(postRoot.left().isLeaf()){
            output += (postRoot.left().element());
            System.out.println("output:" + postRoot.left().element());
            postRoot.setLeft(null);
            State = 2;
            break;
        }else{
            operands.push(postRoot);
            System.out.println("NOT A leaf:" + postRoot.element());
            postRoot = postRoot.left();
            State = 1;
            break;
        }
        case 2: if(postRoot.right().isLeaf()){
            output += (postRoot.right().element());
            System.out.println("output:" + postRoot.right().element());
            postRoot.setLeaf(true);
            if((operands.isEmpty())){
               State = 10;
               output += (postRoot.element());
               break;}
            postRoot = (BinNode)operands.pop();
            State = 1; 
        }else{
            operands.push(postRoot);
            postRoot = postRoot.right();
            State = 1;
            break;
        }
        }
        
    }
        
        return output;
    
    } // end postorder

} // end class
